package main

import "fmt"

/* 21. 合并两个有序链表  https://leetcode.cn/problems/merge-two-sorted-lists/*/

func ExecQ21() {

	var r1, r2 *ListNode

	{
		node4 := &ListNode{Val: 4, Next: nil}
		node2 := &ListNode{Val: 2, Next: node4}
		r1 = &ListNode{Val: 1, Next: node2}

	}

	{
		node4 := &ListNode{Val: 4, Next: nil}
		node3 := &ListNode{Val: 3, Next: node4}
		r2 = &ListNode{Val: 1, Next: node3}

	}
	fmt.Println(mergeTwoLists(r1, r2))
}

// 官方的
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}
